import java.util.List;

public class mySingleList {
    //创建一个内部类
    class ListNode{
        public int val;
        public ListNode next;
        //构造方法
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;//永远指向头结点

    //将  两个 有序 的链表合成 一个 有序的链表
    public ListNode mergeTwoLists(ListNode list1,ListNode list2){
        ListNode newNode = new ListNode(-1);  // 创建一个新结点
        ListNode tmpH = newNode;               // 创建一个移动的尾结点
        while (list1 != null && list2 != null){
            if(list1.val<list2.val){
                tmpH.next = list1;
                tmpH = tmpH.next;
                list1 = list1.next;
            }else {
                tmpH.next = list2;
                tmpH = tmpH.next;
                list2 = list2.next;
            }
        }
        if(list1 != null){
            tmpH.next=list1;
        }else {
            tmpH.next=list2;
        }
        return newNode.next;
    }
    // 以给定值 x 为基准，将链表分割成 两部分，所有小于 x 的结点排在 大于等于 x 结点之前
    public ListNode f(int x){
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while(cur != null){
            if(cur.val<x){
                //判断第一个是否为空
                if(bs == null){
                    bs = cur;
                    be = cur;
                   // cur = cur.next;合并1
                }else{
                    be.next = cur;
                    be = cur;
                    //cur = cur.next;合并1
                }
                cur = cur.next; // 合并1

            }else {
                if(as == null){
                    as = cur;
                    be = cur;
                    //cur = cur.next; // 合并2
                }else{
                    ae.next = cur;
                    ae = cur;
                    //cur = cur.next;// 合并2
                }
                cur = cur.next;    // 合并2
            }

        }
        //最后要将 两个链表链接起来
        if(bs == null){
            return  as;
        }
        if(as != null){
            ae.next = null;     // 手动置空
        }
        be.next = as;
        return bs;

    }
    // 判断链表的回文结果
    public boolean chkPalindrome(){
        // 头结点为空时
        if(head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;

        // 1.找到中间结点,slow 即为中间结点
        while (fast != null && fast.next !=null){
            fast = fast.next;
            slow = slow.next;
        }
        // 2.将中间结点后面的结点翻转
        ListNode cur = slow.next;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.判断回文
        while(head != slow){
            if(head.val != slow.val){
                return false;
            }
            //针对偶数结点
            if(head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    //输出两个链表相交的部分
    public ListNode getIntersationNode(ListNode headA,ListNode headB){
        // 链表有一个为空
        /*if(headA == null && headB != null){
            return null;
        }
        if(headB == null && headA != null){
            return null;
        }*/
        if(headA == null || headB == null){
            return null;
        }
        ListNode plong = headA;  // 假设 A 链表的长度比 B 链表的长度长
        ListNode pshort = headB;
        //分别求两个链表的长度
        int lenth1 = 0;
        int lenth2 = 0;
        //O(M)
        while(headA != null){
            lenth1++;
            headA = headA.next;
        }
        //O(N)
        while(headB != null){
            lenth1++;
            headB = headB.next;
        }
        plong = headA;  // 让它们再次回到头结点
        pshort = headB;
        //2.求长度的差值
        int len = lenth1 - lenth2;
        if(len < 0){
            // 说明 假设不对，B 链表的长度比 A 长
            plong = headB;
            pshort = headA;
            len = lenth2 - lenth1;
            // 让 plong 一定指向最长的链表，pshort 一定指向最短的链表，且 len 一定为正数
        }
        // 3.让长的链表走 len 步
        while (len != 0){
            plong = plong.next;
            len--;
        }
        // 4.一起走，直到相遇
        while(plong != pshort){
            plong = plong.next;
            pshort = pshort.next;
        }
        return plong;// 或者返回 pshort
    }
    // 判断一个链表是否有环
    public boolean hasCycle(ListNode head){
        if(head == null){
            return false;
        }
        // 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 1. fast 走一步，slow 走两步，直到空
        while(fast == null || fast.next == null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;  // 相遇时说明有环
            }
        }
        return false;  // fast 比 slow 要快，若 fast 能走到 空，说明没有环
    }
    //输出环的入口点
    public ListNode detectCycle(ListNode head){
        // 1.判断是否有环
        if(head == null){
            return null;
        }
        // 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 1). fast 走一步，slow 走两步，直到空
        while(fast == null || fast.next == null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;  // 相遇时说明有环
            }
        }
        if(fast == null || fast.next == null) {
            return null;   // 说明没环
        }
        // 有环时
        // 2.从相遇点到 fast 和 slow 再次相遇时，即为环的入口点
        fast = head;  // fast 要重新回到 头结点位置
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;// 或者 slow

    }

}

